//自己
class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) 
    {
        int n = nums.size();
        vector<vector<int>> ret;
        //1. 先排序
        sort(nums.begin(), nums.end());
        //2. 先依次固定一个数 + 前后双指针 + 单调性  (先依次固定一个数, 再用"三数之和"的思想, 再依次固定一个数) 
        for (int i = 0; i < n; i++)
        {
            if (i-1 >= 0 && nums[i] == nums[i-1]) continue;//不能越界 + 去重

            long long  target1 = target - nums[i];//在右边找三个数之和==target1的组合
            for (int j=i+1; j<n; j++)
            {   
                if (j-1 >= i+1 && nums[j] == nums[j-1]) continue;//不能越界(比较的两个值都必须在[i+1, n-1]的范围内) + 去重

                long long target2 = target1 - nums[j]; //有可能会超过int范围
                int left=j+1, right=n-1;
                while (left < right)
                {
                    long long  sum = nums[left] + nums[right];
                    if (sum > target2) --right;
                    else if (sum < target2) ++left;
                    else //sum == target2 
                    {
                        ret.push_back({nums[i], nums[j], nums[left], nums[right]});//initerlizer隐式类型转换
                        //不漏 + 去重 + 不能越界
                        ++left, --right;
                        while (left < right && nums[left] == nums[left-1]) ++left;
                        while (left < right && nums[right] == nums[right+1]) --right;
                    }
                }
            }
        }
        return ret;
    }
};
//时间 O(N*logN + N^3)
//空间 O(logN)


//答案
class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) 
    {
        int n = nums.size();
        vector<vector<int>> ret;
        //1. 先排序
        sort(nums.begin(), nums.end());
        //2. 先依次固定一个数 + 前后双指针 + 单调性  (先依次固定一个数, 再用"三数之和"的思想, 再依次固定一个数) 
        for (int i = 0; i < n; )
        {
            for (int j=i+1; j<n; )
            {   
                long long aim = (long long)target - nums[i] - nums[j]; //有可能会超过int范围,  剩下的两个也都会自动转成long long
                int left=j+1, right=n-1;
                while (left < right)
                {
                    int  sum = nums[left] + nums[right];
                    if (sum > aim) --right;
                    else if (sum < aim) ++left;
                    else //sum == aim 
                    {
                        ret.push_back({nums[i], nums[j], nums[left], nums[right]});//initerlizer隐式类型转换
                        //不漏 + 去重1 + 不能越界
                        ++left, --right;
                        while (left < right && nums[left] == nums[left-1]) ++left;
                        while (left < right && nums[right] == nums[right+1]) --right;
                    }
                }
                //去重2
                ++j;
                while (j<n && nums[j] == nums[j-1]) ++j;
            }
            //去重3
            ++i;
            while (i<n && nums[i] == nums[i-1]) ++i;
        }
        return ret;
    }
};
//时间 O(N*logN + N^3)
//空间 O(logN)